
public class QuickSort extends SortAlgorithmAdapter {

	@Override
	protected void sortArray() {
		qsort();
	}
	
	private void qsort() {
		int len = this.arrayLen;
		
		qsort(0, len - 1);
	}
	
	private void qsort(int start, int end) {
		assert start <= end + 1;
		
		if ( start == end || start == end + 1)	return;
		
		int piv_pos = start;
		
		piv_pos = pivotal_run(start, end, piv_pos);
		
		qsort(start, piv_pos - 1);
		qsort(piv_pos + 1, end);
	}
	
	private int pivotal_run(int start, int end, int pivotal) {
		assert start < end;
		assert start == pivotal;
		
		int good_part_right_boundary = pivotal;
		int piv_pos = pivotal;
		
		while ( good_part_right_boundary < end ) {
			int next = good_part_right_boundary + 1;
			
			assert next <= end;
			
			if ( this.array[next] >= this.array[piv_pos] ) {
				good_part_right_boundary++;
			} else {
				int tmp = this.array[piv_pos];
				this.array[piv_pos] = this.array[next];
				this.array[next] = this.array[piv_pos + 1];
				this.array[piv_pos + 1] = tmp;
				
				piv_pos++;
				
				good_part_right_boundary++;
			}
		}
		
		return piv_pos;
	}
	
}
